PrecSezione 5.3: Errori nelle trasmissioni numeriche di banda base SuCapitolo 5: Trasmissione dati in banda base Sezione 5.5: Protocolli ARQSegue

## 5.4Gestione degli errori di trasmissione

La figura a lato, già proposta a pag. 1↑, ricorda ancora una volta come le conseguenze prodotte dagli errori del decisore, siano alcuni bit diversi da quelli trasmessi. Al § 5.3↑ abbiamo svolto il calcolo della probabilità di errore Pe dovuta a rumore additivo, mentre al § 5.2.2.3↑ è stato illustrato come anche una non perfetta temporizzazione, od una alterazione dell’impulso g(t), possano causare errori di decisione dovuti all’isi. Sempre al primo capitolo è proposta anche la figura replicata appresso, che illustra come la Pe possa essere ridotta adottando tecniche di codifica di canale e controllo di errore, che sono discusse di seguito.

### 5.4.1Controllo di errore↓

Con questo termine si individuano le strategie atte a proteggere le informazioni da trasmettere, aumentando il numero effettivo dei bit inviati (che passano da fb a f’b>fb
bit/secondo, vedi figura), in modo che i bit aggiunti siano dipendenti dagli altri, permettendo la gestione degli eventuali errori di trasmissione.
FEC e ARQ
La quantità di bit aggiunti può permettere di accorgersi della presenza di errori di trasmissione, oppure di correggere detti errori. Se il sistema di trasmissione viene considerato unidirezionale [120] [120]O perchè lo è effettivamente, oppure perchè la trasmissione coinvolge informazioni generate in tempo reale, non memorizzate in trasmissione, e consumate immediatamente in ricezione (ad es. un segnale numerico ottenuto mediante campionamento e quantizzazione), per le quali non ha senso richiedere la trasmissione., lo scopo del controllo di errore è quello di permettere al ricevitore di correggere gli errori che si sono verificati; questo approccio è anche indicato come Forward Error Correction (fec↓, o correzione di errore in avanti), e si è sviluppato nel contesto funzionale della codifica di canale (vedi § 5.4.3↓).
Se al contrario è presente un canale di comunicazione a ritroso, e non sussistono rigidi vincoli temporali sul massimo ritardo tra trasmissione e ricezione corretta, l’effetto di un errore rivelato ma non correggibile immediatamente può essere annullato chiedendo la ritrasmissione del dato errato, dando luogo alle strategie di Automatic Repeat reQuest [121] [121]L’aggettivo automatic si riferisce al fatto che spesso la gestione della ritrasmissione avviene a carico di uno strato protocollare di livello inferiore a quello che effettivamente consuma il messaggio, che in definitiva neanche si avvede della presenza del meccanismo di ritrasmissione. o arq↓ (ossia richiesta automatica di ripetizione) (vedi § 5.5↓), che danno origine alla definizione dei protocolli a finestra, evoluti storicamente nel contesto della trasmissione dati.
Compromesso velocità - distorsione↓
A pag. 1↑ sono svolte delle considerazioni su come l’adozione di tecniche di controllo di errore consenta di contrattare una migliore qualità del segnale ricevuto, a prezzo di una maggiore velocità di trasmissione (e quindi banda occupata) del segnale, mentre al § 17.2↓ è svolta la trattazione analitica relativa a questo fenomeno.

#### 5.4.1.1Errori su parole↓

I metodi di controllo di errore operano tipicamente su gruppi di n bit, ognuno dei quali può rivelarsi sbagliato con probabilità Pe=p; se gli eventi di errore sono statisticamente indipendenti (§ 7.1.5↓), la probabilità di un bit errato su n è pari a np, cioè n volte la probabilità di un bit errato [122] [122] La probabilità che solo il primo bit su n sia sbagliato è pari a p1=p⋅(1  −p)n− 1≃p se p≪1 ed n non è troppo grande; lo stesso risultato si ottiene anche per gli altri n− 1 casi possibili di un bit sbagliato e gli altri corretti, cosicché la probabilità di un solo generico bit sbagliato assomma quelle di tutti i casi..
D’altro canto, la probabilità di i bit errati su n è fornita dalla distribuzione Binomiale (vedi § 8.1↓) P(i,n)=(ni)pi(1  −p)n−i che, se p≪1, può essere approssimata come
(6.52) P(i,n)≈(n(n− 1)⋯(n−i+ 1))/(i!)pi
che è molto inferiore [123] [123]Ad esempio, la probabilità di due bit errati può essere approssimata come (1)/(2)n(n− 1)p2. Infatti, la distribuzione Binomiale fornisce P(2,n)=⎛⎜⎝n 2⎞⎟⎠p2(1 −p)n− 2, in cui ⎛⎜⎝n 2⎞⎟⎠=(n!)/(2!(n− 2)!)=(n(n− 1))/(2) e, se p≪1 ed n non è troppo elevato, (1 −p)n− 2≃1. All’aumentare di p e di n, l’approssimazione non è più valida, e la probabilità di più di un bit errato può risultare maggiore di quella di un solo bit errato. alla probabilità np di un singolo errore su n. Infine, sempre per p≪1, risulta che P(i+ 1,n)≪P(i,n), e quindi si può considerare la probabilità di ricevere i o più bit errati su n, praticamente uguale a quella di osservare solo i errori.
All’aumentare di p e di n, le approssimazioni non sono più valide; in tal caso però, il sistema di trasmissione è praticamente inusabile, e dunque ci si trova sempre nelle condizioni di p sufficentemente piccolo da permettere le approssimazioni.
L’esposizione prosegue illustrando al § 5.4.2↓ tre tecniche utilizzate comunemente per la detezione di errore, e formalizzando quindi (al § 5.4.3↓) il problema della codifica di canale, mediante la descrizione di alcune soluzioni che la realizzano. Infine, al § 5.5↓ sono descritti i protocolli arq adottati nel contesto della trasmissione dati.

### 5.4.2Detezione di errore↓

In questo caso ci si limita a mettere il ricevitore in grado di accorgersi della presenza di errori, senza poterli correggere. Le parole errate possono essere scartate, oppure reinviate su richiesta.

#### 5.4.2.1Parità↓

Viene comunemente usata nell’ambito della trasmissione asincrona e sincrona orientata al carattere, per rivelare errori sul bit, e consiste nell’aggiungere alla parola da trasmettere un ulteriore bit, in modo che in totale ci sia un numero pari di uni [124] [124]Ad esempio, alla sequenza 001001 verrà aggiunto uno 0, mentre a 010101 si aggiungerà ancora un 1, perché altrimenti gli uni complessivi sarebbero stati 3, che è dispari., applicando quindi una regola di parità pari (even). Il caso opposto, ossia l’aggiunta di un bit in modo da rendere dispari il numero di uni, prende nome di parità odd.
In entrambi i casi [125] [125]Il ricevitore deve comunque essere al corrente del fatto se la parità sia odd o even !, quando il ricevitore raggruppa i bit pervenuti, esegue un controllo detto appunto di parità, semplicemente contando il numero di uni, ed accorgendosi così se nella parola si sia verificato un errore (uno zero divenuto uno o viceversa). In tal caso, il ricevitore invierà all’altro estremo del collegamento una richiesta di ritrasmissione del gruppo di bit errati. Se invece si fosse verificato un errore che coinvolge due bit della parola, questo passerebbe inosservato, in quanto la parità prescritta verrebbe mantenuta. Infatti, la distanza di Hamming (vedi pag. 1↓) tra codeword ottenute aggiungendo il bit di parità è pari a due [126] [126]Considerando parole di 3 bit, le codeword (di 4 bit, in cui l’ultimo è una parità pari) risultano: (0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111). E’ facile constatare che ognuna di esse differisce da tutte le altre per due bit..
Esempio: indicando la probabilità di errore sul bit con p (es 10− 3) ed applicando la (6.52↑) si ottiene che la probabilità di i= 2 errori in n bit (es n= 10) vale (1)/(2)n(n− 1)p2 (es 4.5⋅10− 5), e rappresenta il tasso residuo di errore su parola legato all’uso di un bit di parità; la trasmissione di n− 1 bit non protetti sarebbe invece stata esposta ad una probabilità np (es 0.9⋅10− 2) di un bit errato su n.
Il calcolo del bit di parità pari può essere effettuato svolgendo la somma modulo due [127] [127]La somma modulo due è equivalente alla operazione di or esclusivo, viene a volte indicata con il simbolo ⊕, e corrisponde alle definizioni: 0⊕0 = 0, 0⊕1 = 1, 1⊕0 =  1, 1⊕1 = 0. di tutti i bit che compongono la parola (ovvero complementando il risultato, nel caso di parità dispari).

#### 5.4.2.2Somma di controllo↓

Quando il messaggio è composto da M diverse parole di N bit, la probabilità che almeno una di queste sia errata aumenta in modo circa proporzionale ad M, in base ad un ragionamento del tutto analogo a quello della nota 5.4.1.1↑.
Per aumentare le capacità di rivelazione del controllo di parità applicato sulle singole parole (indicato ora come parità di riga, o trasversale), si aggiunge al gruppo di M parole una ulteriore parola (detta somma di controllo), i cui bit si ottengono applicando il controllo di parità a tutti i bit “omologhi” delle M parole incolonnate, generando così una parità di colonna (o longitudinale), come esemplificato in figura.
A volte, si preferisce calcolare la somma di controllo mediante una operazione di somma modulo uno [128] [128]La somma modulo uno è l’equivalente binario dell’operazione di somma (decimale) tradizionale, comprese quindi le operazioni di riporto verso le cifre più elevate. Il riporto finale viene poi nuovamente sommato al risultato della somma., direttamente realizzabile in software in modo veloce. In tal caso, il ricevitore calcola una nuova somma di controllo lungitudinale, includendo anche la somma di controllo originaria: in assenza di errori, il risultato deve fornire zero.

#### 5.4.2.3Codici polinomiali e CRC↓

L’utilizzo di una somma di controllo può produrre risultati scadenti nel caso di distribuzioni temporali dei bit errati particolarmente sfavorevoli, mentre l’uso del Cyclic Redundancy Check (o crc) garantisce prestazioni più uniformi. Questo metodo di con-
trollo di errore consiste nell’aggiungere ad una parola P di k bit che si desidera trasmettere, un gruppo R di m<k ulteriori bit di protezione, calcolati a partire dai primi k, e tali da permettere la detezione di eventuali errori; in questo senso, i codici polinomiali sono classificabili come codici a blocchi (§ 5.4.3.1↓).
L’aggettivo polinomiale trae origine dalla associazione tra un numero binario B di n+ 1 bit, indicati con bi, i= 0, 1, …n, ed un polinomio [129] [129]L’insieme di tutti i polinomi di grado minore od uguale ad n costituisce un particolare spazio algebrico, per il quale è possibile dimostrare una serie di proprietà, la cui verifica trascende dallo scopo di questo testo, e che consentono di stabilire le capacità del codice di rivelare gli errori. B(x) a coefficienti binari nella variabile x, di grado n, con espressione
B(x)=bnxn+bn− 1xn− 1+ …  +b1x1+b0
Un codice polinomiale↓ è definito a partire da un polinomio generatore↓ G(x) di grado m, i cui coefficienti binari identificano una parola G=gmgm− 1…g1g0 di m+ 1 bit.
Indicando ora con P la sequenza dei k bit pi da proteggere, aggiungiamo a destra di questi un gruppo di m bit pari a zero, ottenendo una nuova parola P⋅2m lunga k+m bit, che quindi dividiamo per G (mediante aritmetica modulo due [130] [130]Per fissare le idee, consideriamo k= 8 bit a da proteggere, pari a P=  11100110, m= 4 bit di crc, ed un generatore G= 11001. La sequenza P⋅2m risulta pari a 11100110 0000, e la divisione modulo 2 tra P e G fornisce un quozionte Q= 10110110 (che viene ignorato) ed un resto R pari a 0110. Pertanto, viene trasmessa la sequenza T=P⋅2m⊕R= 11100110 0110 con k+m= 12 bit.
La divisione modulo 2 si realizza come mostrato nella figura a lato, calcolando un or-esclusivo ⊕ bit-a-bit tra i bit più significativi del divisore P, o del resto parziale, e quelli del dividendo G. Per ognuna di queste operazioni, si abbassano una o più cifre binarie del divisore, in modo che il resto parziale abbia la stessa lunghezza del divisore; in tal caso, si ottiene un bit di risultato di quoziente pari ad uno, mentre se il resto parziale è troppo corto, per ogni bit abbassato in più si ottiene un bit di resto parziale pari a zero. Quando tutti i bit del divisore sono stati usati, l’ultima operazione ⊕ fornisce il resto R cercato.
), ottenendo un quoziente Q, ed un resto R con al massimo m bit. Pertanto, possiamo scrivere
(P⋅2m)/(G)=Q⊕(R)/(G)
Le sequenze Q ed R costituiscono rispettivamente i coefficienti dei polinomi quoziente Q(x) e resto R(x), ottenibili dalla divisione di P(x)⋅2m per G(x). Gli m bit R del resto sono quindi utilizzati come parola di protezione, in modo da esprimere la sequenza T da trasmettere come T=P⋅2m⊕R di k+m bit, ovvero con i k bit più elevati pari a P e gli m bit in coda pari ad R. Il ricevitore effettua anch’esso una divisione, stavolta tra T e G, che in assenza di errori produce un resto nullo
(T)/(G)=(P⋅2m⊕R)/(G)=(P⋅2m)/(G)⊕(R)/(G)=Q⊕(R)/(G)⊕(R)/(G)=Q
in quanto sommando in aritmetica modulo due un numero per se stesso, si ottiene un risultato nullo. Pertanto, se T⁄G=Q con resto nullo, la parola P è riottenuta semplicemente shiftando T a destra di m posizioni.
Nel caso invece in cui si siano verificati errori, indichiamo con E la sequenza binaria di errore, di lunghezza k+m bit, ognuno dei quali è pari ad uno se in quella posizione si verifica errore, o zero in caso contrario, in modo da rappresentare il segnale ricevuto R come R=T⊕E. Se E≠ 0 la divisione operata al ricevitore ora fornisce
(R)/(G)=(T⊕E)/(G)=(T)/(G)⊕(E)/(G)=Q⊕(E)/(G)
e quindi si verifica la presenza di un resto pari ad E e diverso da zero, che indica appunto la presenza di errori, tranne nei casi in cui E risulti perfettamente divisibile per G, evento con bassa probabilità se G è scelto oppurtunamente.
Per applicare il metodo, sia il trasmettitore che il ricevitore devono utilizzare lo stesso generatore G(x), per il quale esistono diverse scelte standardizzate [131] [131]Ecco quattro scelte utilizzate nei sistemi di trasmissione:

crc-12 | G(x)=x12+x11+x3+x2+x+  1
crc-16 | G(x)=x16+x15+x2+ 1
crc-ccitt | G(x)=x16+x12+x5+ 1
crc-32 | G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+  1

Come discusso, un polinomio di ordine k genera un crc di k bit; pertanto il crc-12, che è usato per caratteri a 6 bit, genera 12 bit di crc, mentre crc-16 e crc-ccitt, utilizzati in America ed in Europa rispettivamente per caratteri ad 8 bit, producono 16 bit di crc. In alcuni standard di trasmissione sincrona punto-punto, è previsto l’uso di crc-32.. Si può dimostrare che le operazioni discusse permettono di rivelare

- tutti gli errori singoli;
- tutti gli errori doppi se G possiede almeno tre uni;
- qualsiasi numero dispari di errori, se G(x) contiene il fattore (x+ 1);
- tutti gli errori a burst che si estendono per k o meno bit;
- la maggior parte degli errori impulsivi più estesi.

Calcolo del CRC
Gli m bit aggiunti prendono appunto il nome di Cyclic Redundancy Check (o controllo a ridondanza ciclica↓) in virtù del particolare modo in cui questi possono essere calcolati: la parte del procedimento descritto che appare più complessa, ossia la divisione modulo due, è invece quella che ha maggiormente contribuito al successo del metodo, dato che è realizzabile a livello circuitale in modo relativamente semplice [132] [132]Vedi ad es. `http://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks`.
Si tratta infatti di utilizzare un registro a scorrimento controreazionato (vedi figura seguente), in cui sono immessi ad uno ad uno i k bit da proteggere, seguiti da m zeri consecutivi. Per ogni valore immesso, quelli già presenti scorrono a destra nel registro, ed il bit che trabocca alimenta gli or esclusivi presenti nel registro, in corrispondenza degli uni di G(x), tranne che per il bit corrispondente al termine più significativo; l’esempio in figura rappresenta il caso di G(x)=x5+x4+x2+ 1.
Al termine dell’inserimento di k+m bit, lo stato del registro a scorrimento costituisce proprio il resto R, da usare come crc.

### 5.4.3Correzione di errore↓ e codifica di canale↓

Introduciamo ora alcune tecniche di controllo di errore, indicate come codifica di canale, utilizzabili anche per la semplice rivelazione di errore, ma più spesso finalizzate al tentativo di rendere il ricevitore in grado di correggere gli errori sopraggiunti nella trasmissione. L’argomento viene ripreso al § 17.3↓.

#### 5.4.3.1Codice a blocchi↓

La codifica a blocchi opera su blocchi di dati disgiunti, e per ogni gruppo di k bit in ingresso, distinto dagli altri gruppi di k, determina un gruppo di q bit di protezione, dipendenti dai k in ingresso, e che sono inviati assieme ai k originali per un totale di n=n+q bit.
L’operazione compiuta dal codificatore può essere pensata o realizzata come l’accesso ad una tabella memoria (denominata CodeBook↓ = dizionario), dove i k bit da codificare rappresentano un indice che individua 2k differenti righe, in cui si trovano le parole di codice (CodeWord↓), costituite ognuna da n=k+q bit. Un codice siffatto è detto codice (n,k).
Ridondanza↓
Una misura del grado di protezione offerto dal codificatore di canale è rappresentata dalla ridondanza ρ, definita come il rapporto tra il numero di bit di protezione e quelli di informazione, e che è espressa in termini percentuali come
ρ=(q)/(k)⋅100  %
Ad esempio, in una trasmissione con ridondanza del 50%, per ogni due bit di informazione ne viene inserito (da qualche parte) uno di protezione.
Distanza di Hamming↓
L’entità della ridondanza introdotta migliora la capacità del codice di correggere uno o più errori, in quanto non tutte le 2n possibili codeword (di n bit) sono utilizzate, ma solamente 2k tra esse: le configurazioni assenti dal codebook possono comunque presentarsi in ricezione, a causa di errori di trasmissione, ma non essendo previste dal codebook, è possibile rilevare l’errore ed eventualmente correggerlo. Per una determinata coppia di codeword ci,cj, la loro distanza di Hamming dH(ci,cj) è definita come il numero di bit in cui differiscono [133] [133]Valutabile eseguendo il loro or esclusivo ci⊕cj e contando il numero di uni del risultato., e le capacità di rivelazione e correzione di un codice sono quantificate dalla minima dH tra tutte le possibile coppie di codeword dm= mini≠j dH(ci,cj), indicata come distanza del codice↓. Si dimostra infatti che un codice di canale è in grado di correggere (dm− 1)/(2) errori per parola, e di rivelare dm− 1 errori per parola [134] [134]Ad esempio, se d= 3, la presenza di un solo bit errato fa sì che la sequenza ricevuta abbia un solo bit di differenza rispetto alla codeword trasmessa, ed al minimo due bit di differenza rispetto a tutte le altre codeword, permettendo al ricevitore di correggere l’errore. Se invece sono presenti due errori, la procedura di correzione porterebbe a scegliere una codeword errata. Occorre quindi decidere a priori se utilizzare il codice a fini di correzione oppure di detezione, e nel secondo caso, lo stesso codice con d= 3 può rivelare fino a due errori per parola.. Ad un codice a blocchi (n,k) può corrispondere una distanza dm≤n−k+ 1.
Efficienza↓
L’efficienza del codice è misurata dal tasso di codifica↓ (code rate)
Rc=(k)/(n)< 1
che rappresenta la frazione di bit informativi sul totale di quelli trasmessi, e che consente di scrivere la velocità di uscita dal codificatore come
f’b=(fb)/(Rc)>fb
Ad esempio, in una trasmissione con un tasso di codifica pari a 0.5, il numero di bit uscenti (per unità di tempo) dal codificatore di canale è il doppio del numero dei bit entranti.
L’argomento dei codici a blocchi è molto vasto [135] [135]Senza pretesa di esaustività, possiamo annoverare l’esistenza dei codici di Hamming, di Hadamard, BCH, Reed-Solomon, Reed-Muller, di Golay, di Gallager, turbo, a cancellazione, a fontana, punturati..., e fornisce molteplici soluzioni, la cui trattazione esauriente trascende dallo scopo attuale del testo; gli stessi tre casi di controllo di errore già trattati (parità [136] [136]Il concetto di parità può essere il ulteriormente esteso, se ognuno dei k bit aggiunti è calcolato applicando la regola della parità ad un sottoinsieme degli m bit di ingresso, con sottoinsiemi eventualmente sovrapposti. Un codice del genere prende il nome di codice di Hamming, descritto al § 17.3.1.1↓., somma di controllo e crc) possono essere inquadrati nel contesto dei codici a blocchi. Qui ci limitiamo ad un esempio di codice a correzione molto elementare, il codice a ripetizione.

#### 5.4.3.2Codice a ripetizione↓

Un esempio di codice a blocchi molto semplice e con proprietà correttive è il codice a ripetizione n:1, che per ogni bit in arrivo ne produce n identici in uscita, in modo che (se gli errori sono indipendenti) il decisore possa correggere l’errore in base ad una “votazione a maggioranza” (majority voting). Ponendo ad esempio n= 3, definiamo il codice a ripetizione 3:1, composto da due codeword, 000 ed 111, per le quali risulta dm= 3: pertanto, il codice è in grado di correggere un errore e rivelarne due [137] [137]Poniamo di dover trasmettere 0110. La sequenza diventa 000 111 111 000 e quindi, a causa di errori, ricevo 000 101 110 100. Votando a maggioranza, ricostruisco la sequenza corretta 0 1 1 0.. L’esercizio a pag. 1↓ mostra come, se la probabilità di errore per un bit Pe è molto piccola, l’applicazione della decisione a maggioranza permetta di ridurne il valore a Pdece⋍3P2e. Infine, per il codice a ripetizione si ottiene esattamente dm=n−k+ 1, ed essendo k= 1, risulta dm=n, a discapito di un tasso di codifica mediocre, e pari a Rc= 1 ⁄n.

#### 5.4.3.3Errori a burst ed interleaving↓

Figura 5.31  Schema di principio della trasmissione a dati intercalati
Nonostante le capacità di correzione dei codici a blocchi possano sembrare adeguate a ridurre il valore di probabilità di errore, gli errori possono presentarsi in maniera non indipendente, ma concentrati in un breve intervallo di tempo: questa circostanza è indicata come caso degli errori a pacchetto (od a burst=scoppio). In tal caso, si usa ricorrere alla tecnica nota come Scrambling [138] [138]Letteralmente: arrampicamento, ma anche “arruffamento”, vedi scrambled eggs, le uova strapazzate dell’english breakfast. o Interleaving [139] [139]Leave = foglia, sfogliare, rastrellare, ed il termine potrebbe essere tradotto come intercalamento., attuabile a patto di accettare un ritardo di trasmissione. Si tratta infatti di modificare l’ordine dei dati inviati, in modo che gli errori che avvengono su bit vicini si riflettano in errori su bit... lontani e quindi appartenenti a codeword differenti, come illustrato in fig. 5.31↑. Ovviamente, occorre prevedere un processo inverso (descrambling o deinterleaving) all’altro capo del collegamento. E’ appena il caso di notare che lo scrambler (similmente al codice di Gray) non altera il numero dei bit trasmessi.
PrecSezione 5.3: Errori nelle trasmissioni numeriche di banda base SuCapitolo 5: Trasmissione dati in banda base Sezione 5.5: Protocolli ARQSegue